Batch 3 - Class 133 - Invariants 2

• Play a game where the kids start with numbers 1 to 20 on the board. At each step, you erase two numbers and then replace those with a+b-1. Let them do this for 19 steps, and guess the final number as 191. Ask the kids to figure out what's happened
• Answer: The order of choosing numbers is unimportant. The final number is sum of all numbers - number of steps. So 210 - 19 = 191
• What is the invariant?

  Answer: Sum of all numbers - number of numbers (with 20 numbers it is 191, but at the end as well it is 191, and since there is only one number, the number must be 190)

• A statement that does not change from one step to another in a problem
• Must be relevant to solving the problem (for example, "Sum of first five whole numbers is 15" is an invariant for all problems, but it doesn't help solve any problem)
• Is not a constant (for example, "the number of birds" in the sparrow/tree problem - again doesn't help solve the problem)
• Parity is a special case of invariance
• Revision Example: There are six sectors of a disc, with a pawn in each sector. At each step, you take two pawns and move them each to any of the adjacent sectors. Can you get all pawns in the same sector?

• Answer: If you number the six sectors 1..6 in order, then at each step the odd/even parity remains the same. Starting sum is 21, i.e. odd. Getting all six pawns in same sector requires even parity. Hence it is not possible.
• Note that fitting an invariant doesn't guarantee a solution in many cases. Not fitting one can guarantee lack of a solution. (Again, think about irrelevant invariants)

• Now we take the same numbers, and everytime we erase two numbers, we replace that with a+b+ab. What's the final number?
• Whats the invariant? Hint: Can you think of invariant by looking at (a+1)(b+1)...
• Answer: (a+1)(b+1)... is the invariant, so final answer is 24-1=23
• There is an 8x8 table, all squares are white except that one of the squares is colored black. At any step, you take a row or column, and toggle the colors of all squares in that row/column. Prove that you cannot make the entire table white
• Answer: Consider the parity of black colored squares on the table - its an invariant
• Solve the same problem for a 3x3 table with one of the corners black

  Answer: Consider the parity of black colored squares amongst four corners - its an invariant
• Solve the 8x8 table problem if initially the four corners are colored black
• Hint: Go back to the initial problem - generalize to "if there are odd number of black squares on an even grid, it can't be converted to an all-white grid"
• Answer: Consider the 2x2 square in upper left corner. That has odd parity of black colored squares, which is an invariant

• In a special chess game played on 10x10 board, a "Camel" can do a 1,3 move i.e. move 1 square in any direction, and then 3 squares in a perpendicular direction. Is it possible for the camel to move to an adjacent square through a sequence of moves?
• Answer: No. The camel always remains on the same colored square